package leetcode_day._2021._202106._1120;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/20 21:38
 * 皇位继承顺序
 * 算法：树
 */
public class _20_1600 {

    class ThroneInheritance {
        Map<String, List<String>> edges;
        Set<String> set;
        String king;

        public ThroneInheritance(String kingName) {
            edges = new HashMap<>();
            set = new LinkedHashSet<>();
            king = kingName;
        }

        public void birth(String parentName, String childName) {
            List<String> children = edges.getOrDefault(parentName, new ArrayList<>());
            children.add(childName);
            edges.put(parentName, children);
        }

        public void death(String name) {
            set.add(name);
        }

        public List<String> getInheritanceOrder() {
            List<String> ans = new ArrayList<>();
            preOrder(king, ans);
            return ans;
        }
        void preOrder(String pname, List<String> ans) {
            if (!set.contains(pname)) ans.add(pname);
            List<String> children = edges.getOrDefault(pname, new ArrayList<>());
            for (String name : children) preOrder(name, ans);
        }
    }

}
